package org.algorithm.base;

/**
 * 排序算法
 *
 * @author ztranscript 2021/8/27 11:28
 **/
public class SortUtil {
    /**
     * 快速排序
     *
     * @param arr 数组
     * @param l   左边界
     * @param r   右边界
     */
    public static void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        // 先选分界点
        int x = arr[l];
        int i = l - 1, j = r + 1;
        while (i < j) {
            do {
                i++;
            } while (arr[i] < x);
            do {
                j--;
            } while (arr[j] > x);
            if (i < j) {
                swap(arr, i, j);
            }
        }
        // 递归处理左右子数组
        quickSort(arr, l, j);
        quickSort(arr, j + 1, r);
    }

    /**
     * 归并排序
     *
     * @param arr 数组
     * @param l   左边界
     * @param r   右边界
     */
    public static void mergeSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) >> 1;
        // 递归处理两个小数组
        mergeSort(arr, l, mid);
        mergeSort(arr, mid + 1, r);
        // 合并两个已有序的数组
        int p = l, q = mid + 1;
        int[] temp = new int[arr.length];
        for (int i = l; i <= r; i++) {
            if (p <= mid && q <= r) {
                if (arr[p] <= arr[q]) {
                    temp[i] = arr[p++];
                } else {
                    temp[i] = arr[q++];
                }
            } else if (p <= mid) {
                temp[i] = arr[p++];
            } else {
                temp[i] = arr[q++];
            }
        }
        System.arraycopy(temp, l, arr, l, (r - l + 1));
    }

    /**
     * 数组元素交换
     *
     * @param arr 数组
     * @param i   下标
     * @param j   下标
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
